#include <stdio.h>

#include "bitree.h"

// 判断t的左右孩子是否包含有e元素
Status HasChild(BiTree t, ElemType e) {
    if ((t->lchild && t->lchild->data == e) ||
        (t->rchild && t->rchild->data == e)) {
        return TRUE;
    }
    return FALSE;
}

// 非递归先序搜索(DFS)
BiTree PreOrderSearch(BiTree t, ElemType e) {
    SqStack s;
    InitStack(&s);
    while (t || !StackEmpty(&s)) {
        if (t) {
            if (HasChild(t, e)) {
                return t;  // 找到目标结点，返回
            }
            push(&s, t);    // 将当前子树的根结点入栈
            t = t->lchild;  // 优先访问当前子树的左子树
        } else {
            pop(&s, (void**)&t);  // 弹出最近访问子树的根结点
            t = t->rchild;        // 访问当前子树的右子树
        }
    }
    return NULL;
}

// 非递归中序搜索(DFS)
BiTree InOrderSearch(BiTree t, ElemType e) {
    SqStack s;
    InitStack(&s);
    while (t || !StackEmpty(&s)) {
        if (t) {
            push(&s, t);    // 将当前子树的根结点入栈
            t = t->lchild;  // 优先访问当前子树的左子树
        } else {
            pop(&s, (void**)&t);  // 弹出最近访问子树的根结点
            if (HasChild(t, e)) {
                return t;  // 找到目标结点，返回
            }
            t = t->rchild;  // 访问当前子树的右子树
        }
    }
    return NULL;
}

// 非递归后序搜索(DFS)
BiTree PostOrderSearch(BiTree t, ElemType e) {
    SqStack s;
    InitStack(&s);
    BiTree last = NULL;  // 记录最近访问过的结点
    while (t || !StackEmpty(&s)) {
        if (t) {
            push(&s, t);    // 将当前子树的根结点入栈
            t = t->lchild;  // 优先访问当前子树的左子树
        } else {
            GetTop(&s, (void**)&t);  // 取出栈顶结点，不弹出
            if (t->rchild && t->rchild != last) {
                t = t->rchild;  // 当前子树的右子树存在且未被访问过，访问当前子树的右子树
            } else {
                pop(&s, (void**)&t);  // 弹出最近访问子树的根结点
                if (HasChild(t, e)) {
                    return t;  // 找到目标结点，返回
                }
                last = t;  // 记录最近访问过的结点
                t = NULL;  // 置空，继续弹出栈顶结点
            }
        }
    }
    return NULL;
}

BiTree LevelOrderSearch(BiTree t, ElemType e) {
    if (!t) {
        return NULL;  // 空树直接返回
    }
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);
        if (HasChild(p, e)) {
            return p;  // 找到目标结点，返回
        }
        if (p->lchild) {
            EnQueue(&q, p->lchild);  // 如果有左孩子，将左孩子入队
        }
        if (p->rchild) {
            EnQueue(&q, p->rchild);  // 如果有右孩子，将右孩子入队
        }
    }
    return NULL;
}

void TestFindParent(BiTree t, ElemType e) {
    printf("test begin\n");

    BiTree p;

    struct {
        char* name;
        BiTree (*search)(BiTree, ElemType);
    } testFunc[] = {
        {"先序搜索", PreOrderSearch},
        {"中序搜索", InOrderSearch},
        {"后序搜索", PostOrderSearch},
        {"层序搜索", LevelOrderSearch},
    };

    for (int i = 0; i < sizeof(testFunc) / sizeof(testFunc[0]); ++i) {
        printf("%s: ", testFunc[i].name);
        p = testFunc[i].search(t, e);
        if (p) {
            printf("双亲结点为: %c\n", p->data);
        } else {
            printf("找不到双亲结点\n");
        }
    }

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    BiTree r1;
    LevelOrderCreateBiTree(&r1, arr1, 1);
    TestFindParent(r1, 'A');
    TestFindParent(r1, 'B');

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    BiTree r2;
    LevelOrderCreateBiTree(&r2, arr2, 7);
    TestFindParent(r2, 'A');
    TestFindParent(r2, 'B');
    TestFindParent(r2, 'G');
    TestFindParent(r2, 'F');

    return 0;
}